package com.test.nodo;

import org.junit.jupiter.api.Test;

import java.util.Stack;

/**
 * 反转链表 + 查找中间值 + 判断是否有环
 */
public class MyNode {

    private int value;

    private MyNode next;

    public MyNode(int value, MyNode next) {
        this.value = value;
        this.next = next;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public MyNode getNext() {
        return next;
    }

    public void setNext(MyNode next) {
        this.next = next;
    }

    @Test
    public  static  void main(String[] args) {
        // 1->2->3->4
        MyNode next3 = new MyNode(4,null);
        MyNode next2 = new MyNode(3,next3);
        MyNode next1 = new MyNode(2,next2);
        MyNode head = new MyNode(1,next1);

        MyNode myNode = reverse(head);
        print(myNode);
    }

    /**
     * 遍历输出链表的值
     */
    public static void print(MyNode head){
        while(head!=null){
            System.out.println(head.value);
            head = head.next;
        }
    }



    /**
     * 1->2->3->4
     * 4->3->2->1
     */




    public static MyNode reverse3(MyNode head){
        MyNode pre = null;
        while(head!=null){
            MyNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }


    /**
     * 借助栈
     * 反转链表   1>2
     *            2>1
     * // 1->2->3->4   4->3
     * // 4->3->2->1
     */
    public static MyNode reverse2(MyNode head){


        MyNode temp = head;
        MyNode temp1 = head;
        Stack<Integer> stack = new Stack<>();
        while(head!=null){
            stack.add(head.value);
            head = head.next;
        }
       while (temp!=null){
           Integer pop = stack.pop();
           temp.value = pop;
           temp  = temp.next;
       }
        return temp1;

    }

    /**
     * 记住每次只改自己的next指针
     * 反转链表   1>2
     *            2>1
     * // 1->2->3->4   4->3
     * // 4->3->2->1
     */
    public static MyNode reverse1(MyNode head){

        MyNode pre = null;
        MyNode next = null;
        while(head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 记住每次只改自己的next指针
     * 反转链表   1>2
     *            2>1
     * // 1->2->3->4   4->3
     * // 4->3->2->1
     * // reverse 1.next-> reverse 2.next->reverse 3.next -> return 4
     */
    public static MyNode reverse(MyNode head){
        if(   head.next ==null){
            return   head;
        }
        MyNode  temp = head.next;
        // head
        MyNode reverse = reverse(head.next); // reverse 3.next = 4
        temp.next = head;
        head.next = null;
        return reverse;


    }


    /**
     * 1*2*3...*n get 3 1 2 3 get(3) = get(2)* 3 = get(1)*2 = 1*2
     */
    public static int get(int n ){
        if(n==1){
            return 1;
        }
        return get(n - 1)*n;
    }

    @Test
    public void tesGet(){
        int i = get(3);
        System.out.println(i);
    }

    /**
     * 查找中间值
     * @param node
     * @return
     */
    public static Node getMiddle(Node node){
        return new Node(0);
    }

    /**
     * 判断是否有环
     */
    public static boolean isCycle(Node node){
        return false;
    }
}
